Матч 363, Пожатие рук (HandsShaking)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

За круглым столом собрались p бизнесменов. Перед совещанием они должны одновременно пожать друг другу руки. Руки никаких бизнесменов не должны пересекаться. Выяснить, сколькими способами они могут пожать руки друг другу, если p четно.

Класс: HandsShaking

Метод: long long countPerfect(int p)

Ограничения: 2 £ p £ 50, p четное.

Вход. Целое четное число p.

Выход. Количество способов, которыми бизнесмены могут пожать друг другу руки.

Пример входа

p

2

4

8

Пример выхода

1

2

14

РЕШЕНИЕ

числа Каталана

Пронумеруем бизнесменов, сидящих за столом, числами 1, 2, ..., 2*n = p. Обозначим через f(n) количество способов, которыми они могут пожать друг другу руки согласно условию задачи. Рассмотрим все возможные рукопожатия первого бизнесмена. Он может протянуть руку только тому бизнесмену, который имеет четный номер. Если первый бизнесмен протягивает руку (2 * k) - ому, то с одной стороны пересечения их рук останется 2 * k – 2 людей, которые могут пожать руки f(k – 1) способами, а с другой стороны 2 * n – 2 * k людей, которые могут пожать руки f(n – k) способами. Выбирая k = 1, 2, …, n, получим:

f(n) = f(0) * f(n – 1) + f(1) * f(n – 2) + … + f(k – 1) * f(n – k) + … + f(n – 1) * f(0),

f(1) = 1, f(0) = 1

То есть f(n) = являются числами Каталана.

Ответом на задачу будет значение f(p/2).

Значения чисел Каталана вычисляем в массиве cat по приведенной выше формуле:

n	0	1	2	3	4	5	6	7	8	9	10
f(n)	1	1	2	5	14	42	132	429	1430	4862	16796

ПРОГРАММА

#include <stdio.h>

long long cat[51];

class HandsShaking

{

public:

long long countPerfect(int n)

{

int i, j;

cat[0] = cat[1] = 1;

for(i = 2; i <= n; i++)

for(j = 0; j < i; j++)

cat[i] += cat[j] * cat[i - j - 1];

return cat[n/2];

}

};